import UIKit

/*:
 # 链表
 ## Easy
 * [206.反转链表](E206_ReverseList)

 ## Medium
 * [92. 反转链表 II](M092_ReverseList2)
 * [58. 螺旋矩阵](M058_MatrixLink)
 * [24. 两两交换链表中的节点](M024_SwapPairs)

 ## Hard
 * [25. K 个一组翻转链表](H025_ReverseKGroup)

 * [237. 删除链表中的节点](237_DeleteNode)
 * [141. 环形链表](141_ListHasCycle)
 * [203. 移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements/)
 * [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)
 * [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/)
 */

/// 1. 递归反转链表
func reverseList(head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }

    let last = reverseList(head: head?.next)
    head?.next?.next = head
    head?.next = nil
    return last
}

// 2. 反转前n个链表
// 记录反转前n个后的节点
var successor: ListNode?
func reverseN(head: ListNode?, n: Int) -> ListNode? {
    if n == 1 {
        // 记录n+1个节点
        successor = head?.next
        return head
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    let last = reverseN(head: head?.next, n: n-1)
    head?.next?.next = head
    // 让反转之后的 head 节点和后面的节点连起来
    head?.next = successor
    return last
}

// 3. 反转链表一部分
func reverseBetween(head: ListNode?, m: Int, n: Int) -> ListNode? {
    // base case
    if m == 1 {
        return reverseN(head: head, n: n)
    }
    // 前进到反转的起点触发 base case
    head?.next = reverseBetween(head: head?.next, m: m-1, n: n)
    return head
}
